Chris Pollett >Old Classes >
CS254
( Print View )

Grades: [Sec1]

Course Info:
  [Texts & Links]
  [Topics]
  [Grading]
  [HW Info]
  [Exam Info]
  [Regrades]
  [Honesty]
  [Announcements]

HW Assignments:
  [Hw1]  [Hw2]  [Hw3]
  [Hw4]  [Hw5]

Practice Exams:
  [Mid1]  [Mid2]  [Final] 

                           












HW#5 --- last modified January 01 1970 00:00:00..

Due date: May 7

Purpose: To get more familiar with probabilistic complexity classes, circuit classes, and to start learning a little about complexity related to cryptography.

Specification:

Do the following problems 11.5.16, 12.3.7, 14.5.9, 17.3.8 out of the book
then solve:

5. Exhibit an oracle A under which NP ∩ coNP has complete problems, yet NPA=/=PA.

Point Breakdown

Each problem is worth 2pts 10pt
Total 10pts